/**
 * Project Name:JavaBaseReview
 * Package Name:com.xuwei.base.search
 * author:David
 * Date:2016年5月20日上午8:19:08
 * Copyright (c) 2016, xw123box@126.com All Rights Reserved.
 *
 */
package com.xuwei.base.search;

/**
 * @author David
 * @since 2016年5月20日 上午8:19:08
 * @version 
 * @since JDK 1.6
 */
public class BinSearch {
	/**
	 * 折半查找的非递归形式实现
	 */
	public static int binSearch1(int[] s ,int low, int high, int key){
		while(low<=high){
			int mid = (low + high)/2;
			if(s[mid]==key){
				return mid;
			}else if(s[mid]>key){
				high = mid -1;
			}else{
				low = mid +1;
			}
		}
		return -1;
	}
	
	/**
	 * 折半查找的递归形式实现
	 */
	public static int binSearch2(int[] s, int low, int high, int key){
		if(low<=high){
			int mid = (low + high)/2;
			if(s[mid]==key){
				return mid;
			}else if(s[mid]>key){
				return binSearch2(s, low, mid-1, key);
			}else{
				return binSearch2(s, low+1, high, key);
			}
		}
		return -1;
	}
	
	public static void main(String[] args) {
		int[] arr = {1,3,8,11,22};
		System.out.println(binSearch2(arr, 0, arr.length-1, 8));
	}
	
	
	

}
